package graph;

import java.util.*;

/**
 * 我的dijkstra算法实现
 */
public class MyDijkstraLiked {

    public static class Vertex {
        //相邻节点
        int node;
        //权重
        int weight;

        public Vertex(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
    }

    /**
     * 求最短路径
     */
    public static List<Integer> dijkstra(Map<Integer, LinkedList<Vertex>> graph, Integer start, Integer end) {
        Map<Integer, Integer> costs = new HashMap<>();
        Map<Integer, Boolean> visited = new HashMap<>();
        Map<Integer, Integer> parents = new HashMap<>();

        //初始化开销
        for (Integer node : graph.keySet()) {
            costs.put(node, Integer.MAX_VALUE);
            visited.put(node, false);
        }
        //初始化起点的开销为零
        costs.put(start, 0);

        //最多遍历除终点的所有节点
        for (int i = 0; i < graph.size() - 1; i++) {

            //获取没有访问的开销最小的点
            Integer lowestNode = null;
            Integer lowestCost = Integer.MAX_VALUE;
            for (Map.Entry<Integer, Integer> entry : costs.entrySet()) {
                if (!visited.get(entry.getKey()) && lowestCost > entry.getValue()) {
                    //这样可以避开没有访问但是开销已经很大的路径
                    if (entry.getValue() < costs.get(end)) {
                        lowestNode = entry.getKey();
                        lowestCost = entry.getValue();
                    }
                }
            }

            //没有符合条件的提前结束
            if (lowestNode == null) {
                break;
            }

            visited.put(lowestNode, true);

            // 更新相邻节点的开销
            for (Vertex vertex : graph.get(lowestNode)) {
                Integer cost = costs.get(vertex.node);
                Integer nextCost = lowestCost + vertex.weight;
                if (nextCost < cost) {
                    costs.put(vertex.node, nextCost);
                    parents.put(vertex.node, lowestNode);
                }
            }
        }

        // 根据parents关系，连接成起点到终点的路径
        List<Integer> lowestPath = new LinkedList<>();
        int cur = end;
        lowestPath.add(cur);
        while (!Objects.equals(cur = parents.get(cur), start)) {
            lowestPath.add(0, cur);
        }
        lowestPath.add(0, cur);
        return lowestPath;
    }

    public static void main(String[] args) {
        Map<Integer, LinkedList<Vertex>> graph = new HashMap<>();
        //表示0节点到1节点的距离为2，到2节点的距离为4
        graph.put(0, new LinkedList<>());
        graph.put(1, new LinkedList<>());
        graph.put(2, new LinkedList<>());
        graph.put(3, new LinkedList<>());
        graph.put(4, new LinkedList<>());
        graph.put(5, new LinkedList<>());

        graph.get(0).add(new Vertex(1, 2));
        graph.get(0).add(new Vertex(2, 4));

        graph.get(1).add(new Vertex(2, 1));
        graph.get(1).add(new Vertex(3, 4));
        graph.get(1).add(new Vertex(4, 2));

        graph.get(2).add(new Vertex(4, 3));

        graph.get(3).add(new Vertex(4, 3));
        graph.get(3).add(new Vertex(5, 2));

        graph.get(4).add(new Vertex(5, 2));

        System.out.println(dijkstra(graph, 0, 5));
    }
}
